﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace AGPFP1
{
    class AGPFP
    {

        public string texto;
        public int poblacion;
        public List<List<int[]>> pueblo = new List<List<int[]>>();
        List<int[]> listaOperadores = new List<int[]>();

        public AGPFP(string texto, int poblacion)
        {
            this.texto = texto;
            this.poblacion = poblacion;

        }//constructor

        public void generarPoblacionInicial2D()
        {

            for (int i = 0; i < poblacion; i++)
            {

                pueblo.Add(generarSolucionAleatoriaGenerica2D(new List<int[]>(), new int[]{0,0}, this.texto.Length));

            }

            //Console.WriteLine("Poblacion inicial generada");

        }

        private Random generadorAleatorio = new Random();

        public List<int[]> generarSolucionAleatoriaGenerica2D(List<int[]> camino, int[] coordenadaInicial, int tamanoFinal)
        {


            camino.Add(coordenadaInicial);

            List<int[]> copiaCamino = new List<int[]>();
            copiaCamino.AddRange(camino);
            int[] copiaCoordenadaInicial = coordenadaInicial;

            coordenadaInicial = generarCoordenadaNueva2D(coordenadaInicial);
            int n = 0;


            while (camino.Count < tamanoFinal)
            {

                n++;

                while (contieneGenerico2D(camino, coordenadaInicial))
                {
                    if (estaBloqueado2D(camino))
                        break;

                    coordenadaInicial = generarCoordenadaNueva2D((int[])camino[camino.Count - 1]);
                }


                if (estaBloqueado2D(camino))
                {
                    camino = new List<int[]>();
                    camino.AddRange(copiaCamino);

                    coordenadaInicial = copiaCoordenadaInicial;
                }
                else
                {
                    camino.Add(coordenadaInicial);
                }

                if (n > 1000)
                {
                    Console.WriteLine("Camino bloqueado, generando camino nuevo... " + camino.Count + " = " + tamanoFinal);


                    camino = new List<int[]>();

                    camino = this.generarSolucionAleatoriaGenerica2D(camino, new int[] { 0, 0 }, this.texto.Length);
                    break;

                    //this.generar2d(camino, "HPHPHHPHP", "YA WEEEEEY");
                }

            }


            return camino;


        }//fin metodo generarSolucionAleatoriaGenerica

        private int[] generarCoordenadaNueva2D(int[] coordenada)
        {

            int[] cNueva = new int[2];

            int numAleatorio = this.generadorAleatorio.Next(4);

            if (numAleatorio == 0)
            {
                cNueva[0] = coordenada[0] + 1;
                cNueva[1] = coordenada[1];

            }
            else if (numAleatorio == 1)
            {
                cNueva[0] = coordenada[0] - 1;
                cNueva[1] = coordenada[1];

            }
            else if (numAleatorio == 2)
            {
                cNueva[0] = coordenada[0];
                cNueva[1] = coordenada[1] + 1;

            }
            else
            {
                cNueva[0] = coordenada[0];
                cNueva[1] = coordenada[1] - 1;

            }

            return cNueva;
        }//  fin generar coordenada aleatoria

        private bool estaBloqueado2D(List<int[]> camino)
        {

            int[] coordenada = (int[])camino[camino.Count - 1];

            int[] coordenada1 = new int[2];
            int[] coordenada2 = new int[2];
            int[] coordenada3 = new int[2];
            int[] coordenada4 = new int[2];

            coordenada1[0] = coordenada[0];
            coordenada1[1] = coordenada[1] + 1;

            coordenada2[0] = coordenada[0];
            coordenada2[1] = coordenada[1] - 1;

            coordenada3[0] = coordenada[0] + 1;
            coordenada3[1] = coordenada[1];

            coordenada4[0] = coordenada[0] - 1;
            coordenada4[1] = coordenada[1];

            return (contieneGenerico2D(camino, coordenada1) && contieneGenerico2D(camino, coordenada2)
                && contieneGenerico2D(camino, coordenada3) && contieneGenerico2D(camino, coordenada4));


        }//fin estaBloqueado

        private bool contieneGenerico2D(List<int[]> camino, int[] c)
        {

            bool bandera = false;

            foreach (int[] i in camino)
            {

                if (i[0] == c[0] &&
                    i[1] == c[1])
                {
                    bandera = true;

                }

            }

            return bandera;

        }//fin metodo contieneGenerico

        public int evaluarCamino2D(List<int[]> camino)
        {

            int[] primero = new int[2];
            int[] siguiente = new int[2];
            int energia = 0;




            for (int j = 0; j < camino.Count; j++)
            {

                primero = (int[])camino[j];

                for (int i = j + 2; i < camino.Count - 1 + 1; i++)
                {
                    siguiente = (int[])camino[i];
                    if (distancia(primero[0], primero[1], siguiente[0], siguiente[1], j, i) == 1)
                    {
                        energia--;

                    }

                }

                //Console.WriteLine ("AY MI DIOS");
            }

            return energia;
            //contador++;

        }//fin funcionEnergia

        private int distancia(int x1, int y1, int x2, int y2, int letra1, int letra2)
        {

            if (letra2 >= texto.Length)
                return 0;

            int e = 0;

            if ((texto[letra1] == texto[letra2])
                && (texto[letra1] == 'H'))
            {
                if ((Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2)) == 1)
                    e = 1;

            }



            return e;

        }//fin metodo distancia

        public double mediaPoblacion2D()
        {
            double media = 0;

            foreach(List<int[]> camino in this.pueblo)
            {
                media += this.evaluarCamino2D(camino);
                //Console.WriteLine(evaluarCamino2D(camino));
            }

            media = media / this.poblacion;

            return media;
        }

        public void mejorarMedia2D()
        {

            List<List<int[]>> puebloNuevo = new List<List<int[]>>();
            

            foreach (List<int[]> camino in this.pueblo)
            {
                List<int[]> c1 = new List<int[]>();
                List<int[]> c2 = new List<int[]>();
                c1.AddRange(camino);
                c2.AddRange(camino);

                for (int L1 = 0; L1 <= 500; L1++)//OPERADORES
                {


             
                    this.buscarOperadores(c2);

                    if (listaOperadores.Count != 0)
                    {
                        c2 = operadorAleatorio(c2);

                    }
                    else
                    {
                        c2 = generarSolucionAleatoriaGenerica2D(new List<int[]>(), new int[] { 0, 0 }, this.texto.Length);
                        //Console.WriteLine("asi es");
                    }
                   

                    if (this.evaluarCamino2D(c2) < this.evaluarCamino2D(c1))
                    {
                        c1.Clear();
                        c1.AddRange(c2);

                    }

                }//fin for 300

                puebloNuevo.Add(c1);

            }//for each

            this.pueblo.Clear();
            this.pueblo.AddRange(puebloNuevo);
            
        }

        public int[] mover(int[] coordenada, string direccion)
        {

            int[] salida = new int[2];
            salida[0] = coordenada[0];
            salida[1] = coordenada[1];

            if (direccion.Equals("arriba"))
            {
                salida[1] = salida[1] + 1;
            }
            else if (direccion.Equals("abajo"))
            {
                salida[1] = salida[1] - 1;
            }
            else if (direccion.Equals("izquierda"))
            {
                salida[0] = salida[0] - 1;
            }
            else
            {
                salida[0] = salida[0] + 1;
            }

            return salida;
        }

        public void buscarOperadores(List<int[]> camino)
        {


            //int eleccion = generadorAleatorio.Next(camino.Count);

            //eleccion = 0;

            /**
             * 0-3 = operador esquina
             * 4-7 = operador multiple
             * 8-13 = operador orilla
             */

            /* Si sale para operador movimiento multiple A-B-C-D-0-0-0-0-0-....-A-B-C-D
             * Si sale para operador esquina entonces A-B-C-0-0-0-0-0-0-....-A-B-C
             * Si sale para operador orilla: A-B-0-0-0-0-.....-As-Bs
             * Seleccionar B aleatorio, debe estar entre 1 y tamaño del camino - 2 para operador movimiento multiple
             * Seleccion B aleatorio, debe estar entre 1 y tamaño del camino - 1 para esquina
             */

            /*
             * operador1 = 1
             * operador2 = 2
             * operador3 = 3
             * operador4 = 4
             * Moperador1 = 5
             * Moperador2 = 6
             * Moperador3 = 7
             * Moperador4 = 8
             * Soperador1-1 = 9
             * Soperador1-2 = 10
             * Soperador2-1 = 11
             * Soperador2-2 = 12
             * Soperador3-1 = 13
             * Soperador3-2 = 14
             * Soperador4-1 = 15
             * Soperador4-2 = 16
             * 
             */

            listaOperadores = new List<int[]>();
            ArrayList instrucciones = new ArrayList();
            int[] A = null;
            int[] B = null;
            int[] C = null;
            int[] D = null;
            int[] As = null;
            int[] Bs = null;
            int[] X = null;
            int[] Y = null;





            ////////////OPERADORES ESQUINA////////////////


            for (int a = 1; a <= camino.Count - 2; a++)
            {

                A = (int[])camino[a - 1];
                B = (int[])camino[a];
                C = (int[])camino[a + 1];


                //operador1

                X = mover(A, "derecha");

                // MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] X = [" + X[0] + "," + X[1] + "]");

                if ((mover(B, "arriba")[0] == A[0]) &&
                    (mover(B, "arriba")[1] == A[1]) &&
                    (mover(B, "derecha")[0] == C[0]) &&
                    (mover(B, "derecha")[1] == C[1]) &&
                    !contieneGenerico2D(camino, X))
                {

                    listaOperadores.Add(new int[] { 1, a });
                    instrucciones.Add("operador1 aplicable a: [" + B[0] + "," + B[1] + "]");

                }



                //operador2




                X = mover(C, "abajo");

                // MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] X = [" + X[0] + "," + X[1] + "]");

                if ((mover(B, "abajo")[0] == A[0]) &&
                    (mover(B, "abajo")[1] == A[1]) &&
                    (mover(B, "derecha")[0] == C[0]) &&
                    (mover(B, "derecha")[1] == C[1]) &&
                    !contieneGenerico2D(camino, X))
                {
                    listaOperadores.Add(new int[] { 2, a });
                    instrucciones.Add("operador2 aplicable a: [" + B[0] + "," + B[1] + "]");
                }




                //operador3



                X = mover(A, "abajo");

                // MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] X = [" + X[0] + "," + X[1] + "]");

                if ((mover(B, "izquierda")[0] == A[0]) &&
                    (mover(B, "izquierda")[1] == A[1]) &&
                    (mover(B, "abajo")[0] == C[0]) &&
                    (mover(B, "abajo")[1] == C[1]) &&
                    !contieneGenerico2D(camino, X))
                {
                    listaOperadores.Add(new int[] { 3, a });
                    instrucciones.Add("operador3 aplicable a: [" + B[0] + "," + B[1] + "]");
                }





                //operador4



                X = mover(A, "arriba");

                // MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] X = [" + X[0] + "," + X[1] + "]");

                if ((mover(B, "izquierda")[0] == A[0]) &&
                    (mover(B, "izquierda")[1] == A[1]) &&
                    (mover(B, "arriba")[0] == C[0]) &&
                    (mover(B, "arriba")[1] == C[1]) &&
                    !contieneGenerico2D(camino, X))
                {
                    listaOperadores.Add(new int[] { 4, a });
                    instrucciones.Add("operador3 aplicable a: [" + B[0] + "," + B[1] + "]");

                }



            }//fin for

            ////////////OPERADORES MOVIMIENTO MULTIPLE////////////////

            //Moperador1


            for (int a = 1; a <= camino.Count - 3; a++)
            {
                A = (int[])camino[a - 1];
                B = (int[])camino[a];
                C = (int[])camino[a + 1];
                D = (int[])camino[a + 2];


                X = mover(B, "derecha");
                Y = mover(X, "abajo");

                if ((mover(B, "abajo")[0] == A[0]) &&
                    (mover(B, "abajo")[1] == A[1]) &&
                    (mover(B, "arriba")[0] == C[0]) &&
                    (mover(B, "arriba")[1] == C[1]) &&
                    (mover(C, "derecha")[0] == D[0]) &&
                    (mover(C, "derecha")[1] == D[1]) &&
                    !contieneGenerico2D(camino, X) &&
                    !contieneGenerico2D(camino, Y))
                {

                    listaOperadores.Add(new int[] { 5, a });
                    instrucciones.Add("Moperador1 aplicable a: [" + B[0] + "," + B[1] + "] y [" + C[0] + "," + C[1] + "]");
                }



                //Moperador2

                X = mover(A, "abajo");
                Y = mover(X, "abajo");

                if ((mover(B, "izquierda")[0] == A[0]) &&
                    (mover(B, "izquierda")[1] == A[1]) &&
                    (mover(B, "abajo")[0] == C[0]) &&
                    (mover(B, "abajo")[1] == C[1]) &&
                    (mover(C, "abajo")[0] == D[0]) &&
                    (mover(C, "abajo")[1] == D[1]) &&
                    !contieneGenerico2D(camino, X) &&
                    !contieneGenerico2D(camino, Y))
                {
                    listaOperadores.Add(new int[] { 6, a });
                    instrucciones.Add("Moperador2 aplicable a: [" + B[0] + "," + B[1] + "] y [" + C[0] + "," + C[1] + "]");
                }


                //Moperador3

                X = mover(A, "arriba");
                Y = mover(X, "arriba");

                // MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] D= [" + D[0] + "," + D[1] + "] X = [" + X[0] + "," + X[1] + "] Y= [" + Y[0] + "," + Y[1] + "]");

                if ((mover(B, "izquierda")[0] == A[0]) &&
                    (mover(B, "izquierda")[1] == A[1]) &&
                    (mover(B, "arriba")[0] == C[0]) &&
                    (mover(B, "arriba")[1] == C[1]) &&
                    (mover(C, "arriba")[0] == D[0]) &&
                    (mover(C, "arriba")[1] == D[1]) &&
                    !contieneGenerico2D(camino, X) &&
                    !contieneGenerico2D(camino, Y))
                {
                    listaOperadores.Add(new int[] { 7, a });
                    instrucciones.Add("Moperador3 aplicable a: [" + B[0] + "," + B[1] + "] y [" + C[0] + "," + C[1] + "]");
                }




                //Moperador4



                X = mover(B, "derecha");
                Y = mover(X, "arriba");

                //MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] D= [" + D[0] + "," + D[1] + "] X = [" + X[0] + "," + X[1] + "] Y= [" + Y[0] + "," + Y[1] + "]");

                if ((mover(B, "arriba")[0] == A[0]) &&
                    (mover(B, "arriba")[1] == A[1]) &&
                    (mover(B, "abajo")[0] == C[0]) &&
                    (mover(B, "abajo")[1] == C[1]) &&
                    (mover(C, "derecha")[0] == D[0]) &&
                    (mover(C, "derecha")[1] == D[1]) &&
                    !contieneGenerico2D(camino, X) &&
                    !contieneGenerico2D(camino, Y))
                {
                    listaOperadores.Add(new int[] { 8, a });
                    instrucciones.Add("Moperador4 aplicable a: [" + B[0] + "," + B[1] + "] y [" + C[0] + "," + C[1] + "]");
                }


            }//fin for

            ////////////OPERADORES ORILLA////////////////

            //Soperador1


            A = (int[])camino[0];
            B = (int[])camino[1];

            As = (int[])camino[camino.Count - 1];
            Bs = (int[])camino[camino.Count - 2];


            X = mover(B, "derecha");

            //MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] D= [" + D[0] + "," + D[1] + "] X = [" + X[0] + "," + X[1] + "] Y= [" + Y[0] + "," + Y[1] + "]");

            if ((mover(B, "arriba")[0] == A[0]) &&
                (mover(B, "arriba")[1] == A[1]) &&
                !contieneGenerico2D(camino, X))
            {
                listaOperadores.Add(new int[] { 9, 0 });
                instrucciones.Add("Soperador1-1 aplicable a: [" + B[0] + "," + B[1] + "]");
            }

            X = mover(Bs, "derecha");

            //MessageBox.Show("A = [" + A[0] + "," + A[1] + "] B =[" + B[0] + "," + B[1] + "] C= [" + C[0] + "," + C[1] + "] D= [" + D[0] + "," + D[1] + "] X = [" + X[0] + "," + X[1] + "] Y= [" + Y[0] + "," + Y[1] + "]");

            if ((mover(Bs, "arriba")[0] == As[0]) &&
                (mover(Bs, "arriba")[1] == As[1]) &&
                !contieneGenerico2D(camino, X))
            {
                listaOperadores.Add(new int[] { 10, camino.Count - 1 });
                instrucciones.Add("Soperador1-2 aplicable a: [" + B[0] + "," + B[1] + "]");

            }

            //Soperador2


            X = mover(B, "izquierda");


            if ((mover(B, "arriba")[0] == A[0]) &&
                (mover(B, "arriba")[1] == A[1]) &&
                !contieneGenerico2D(camino, X))
            {

                listaOperadores.Add(new int[] { 11, 0 });
                instrucciones.Add("Soperador2-1 aplicable a: [" + B[0] + "," + B[1] + "]");
            }

            X = mover(Bs, "izquierda");


            if ((mover(Bs, "arriba")[0] == As[0]) &&
                (mover(Bs, "arriba")[1] == As[1]) &&
                !contieneGenerico2D(camino, X))
            {

                listaOperadores.Add(new int[] { 12, camino.Count - 1 });
                instrucciones.Add("Soperador2-2 aplicable a: [" + B[0] + "," + B[1] + "]");
            }


            //Soperador3


            X = mover(B, "arriba");


            if ((mover(B, "izquierda")[0] == A[0]) &&
                (mover(B, "izquierda")[1] == A[1]) &&
                !contieneGenerico2D(camino, X))
            {

                listaOperadores.Add(new int[] { 13, 0 });
                instrucciones.Add("Soperador3-1 aplicable a: [" + B[0] + "," + B[1] + "]");
            }

            X = mover(Bs, "arriba");


            if ((mover(Bs, "izquierda")[0] == As[0]) &&
                (mover(Bs, "izquierda")[1] == As[1]) &&
                !contieneGenerico2D(camino, X))
            {

                listaOperadores.Add(new int[] { 14, camino.Count - 1 });
                instrucciones.Add("Soperador3-1 aplicable a: [" + B[0] + "," + B[1] + "]");
            }


            //Soperador4

            X = mover(B, "arriba");


            if ((mover(B, "derecha")[0] == A[0]) &&
                (mover(B, "derecha")[1] == A[1]) &&
                !contieneGenerico2D(camino, X))
            {

                listaOperadores.Add(new int[] { 15, 0 });
                instrucciones.Add("Soperador3-2 aplicable a: [" + B[0] + "," + B[1] + "]");
            }

            X = mover(Bs, "arriba");


            if ((mover(Bs, "derecha")[0] == As[0]) &&
                (mover(Bs, "derecha")[1] == As[1]) &&
                !contieneGenerico2D(camino, X))
            {

                listaOperadores.Add(new int[] { 16, camino.Count - 1 });
                instrucciones.Add("Soperador4-1 aplicable a: [" + B[0] + "," + B[1] + "]");
            }



            //foreach (KeyValuePair<int, int> valor in listaOperadores)
            //{

            //    instrucciones.Add("Operador = " + valor.Key + " en la posicion = " + valor.Value);


            //}




        }//fin buscar operadores

        public List<int[]> operadorAleatorio(List<int[]> camino)
        {


            //int eleccion = generadorAleatorio.Next(camino.Count);

            //eleccion = 0;

            /**
             * 0-3 = operador esquina
             * 4-7 = operador multiple
             * 8-13 = operador orilla
             */

            /* Si sale para operador movimiento multiple A-B-C-D-0-0-0-0-0-....-A-B-C-D
             * Si sale para operador esquina entonces A-B-C-0-0-0-0-0-0-....-A-B-C
             * Si sale para operador orilla: A-B-0-0-0-0-.....-As-Bs
             * Seleccionar B aleatorio, debe estar entre 1 y tamaño del camino - 2 para operador movimiento multiple
             * Seleccion B aleatorio, debe estar entre 1 y tamaño del camino - 1 para esquina
             */

            int[] A = null;
            int[] B = null;
            int[] C = null;
            int[] D = null;
            int[] As = null;
            int[] Bs = null;
            int[] X = null;
            int[] Y = null;

            As = (int[])camino[camino.Count - 1];
            Bs = (int[])camino[camino.Count - 2];
            B = (int[])camino[1];


            int aleatorio = generadorAleatorio.Next(listaOperadores.Count);

            int eleccion = listaOperadores[aleatorio][0];

            int a = listaOperadores[aleatorio][1];

            // Console.WriteLine("Se aplicara operador " + eleccion + " en el numero " + a);

            //using (System.IO.StreamWriter file = new System.IO.StreamWriter(@"salida.txt", true))
            //{
            //    //file.WriteLine("Encontro: (" + loMejorcito[0] + "," + loMejorcito[1] + ") [" + loMejorcitoSencillo + "]");
            //    file.WriteLine(eleccion);
            //}

            switch (eleccion)
            {

                case 1://operador1

                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];


                    X = mover(A, "derecha");
                    camino[a] = X;
                    break;



                case 2://operador2


                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];


                    X = mover(C, "abajo");
                    camino[a] = X;
                    break;


                case 3://operador3


                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];


                    X = mover(A, "abajo");
                    camino[a] = X;
                    break;


                case 4://operador4

                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];


                    X = mover(A, "arriba");
                    camino[a] = X;
                    break;

                case 5://Moperador1


                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];
                    D = (int[])camino[a + 2];


                    X = mover(B, "derecha");
                    Y = mover(X, "abajo");
                    camino[a] = Y;
                    camino[a + 1] = X;
                    break;


                case 6://Moperador2

                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];
                    D = (int[])camino[a + 2];


                    X = mover(A, "abajo");
                    Y = mover(X, "abajo");
                    camino[a] = X;
                    camino[a + 1] = Y;
                    break;


                case 7://Moperador3


                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];
                    D = (int[])camino[a + 2];


                    X = mover(A, "arriba");
                    Y = mover(X, "arriba");
                    camino[a] = X;
                    camino[a + 1] = Y;
                    break;

                case 8://Moperador4


                    A = (int[])camino[a - 1];
                    B = (int[])camino[a];
                    C = (int[])camino[a + 1];
                    D = (int[])camino[a + 2];


                    X = mover(B, "derecha");
                    Y = mover(X, "arriba");


                    camino[a] = Y;
                    camino[a + 1] = X;
                    break;

                case 9://Soperador1


                    X = mover(B, "derecha");



                    camino[0] = X;
                    break;

                case 10:

                    X = mover(Bs, "derecha");
                    camino[camino.Count - 1] = X;
                    break;

                case 11://Soperador2

                    X = mover(B, "izquierda");
                    camino[0] = X;
                    break;

                case 12:

                    X = mover(Bs, "izquierda");
                    camino[camino.Count - 1] = X;
                    break;

                case 13://Soperador3

                    X = mover(B, "arriba");
                    camino[0] = X;
                    break;

                case 14:

                    X = mover(Bs, "arriba");
                    camino[camino.Count - 1] = X;
                    break;

                case 15://Soperador4

                    X = mover(B, "arriba");
                    camino[0] = X;
                    break;

                case 16:

                    X = mover(Bs, "arriba");
                    camino[camino.Count - 1] = X;
                    break;

            }//fin switch



            return camino;

        }//fin 

        public List<int[]> cruzar(List<int[]> padre1, List<int[]> padre2)
        {
            List<int[]> mitadPadre1 = new List<int[]>();
            List<int[]> mitadPadre2 = new List<int[]>();
            List<int[]> elMejor = new List<int[]>();
            List<int[]> elEngendroDelMal = new List<int[]>();
            elMejor.AddRange(padre1);
            string textoPadre1 = "";
            string textoPadre2 = "";
            int limite = 0;
            bool hayaMaldad = true;


            while (hayaMaldad) { //Si no se pudo con ninguna condicion entonces de nuevo intentara el corte en otro lado

                hayaMaldad = false;
                int cortePadre1 = generadorAleatorio.Next(padre1.Count - 3); //para que no salgan cadenas de 2
                int cortePadre2 = cortePadre1++;
                int contador = 0;

                foreach (int[] a in padre1)
                {

                    if (contador <= cortePadre1)
                        mitadPadre1.Add(a);
                    contador++;
                }

                contador = 0;

                foreach (int[] a in padre2)
                {

                    if (contador > cortePadre1)
                        mitadPadre2.Add(a);
                    contador++;
                }

                contador = 0;
                foreach (char a in texto)
                {
                
                    if (contador <= cortePadre1)
                        textoPadre1 += a;
                    else
                        textoPadre2 += a;

                    contador++;
                }
           
            
            
                //Console.WriteLine("Padre 1: " + mitadPadre1.Count + "=" + textoPadre1.Count());
                //Console.WriteLine("Padre 2: " + mitadPadre2.Count + "=" + textoPadre2.Count());
                //Console.WriteLine(texto);
                //Console.WriteLine(textoPadre1 + "-" + textoPadre2);

                //Console.WriteLine("Corte en: " + cortePadre1);
                //dibujar(padre1, this.texto, "Padre 1");
                //dibujar(padre2, this.texto, "Padre 2");
                //dibujar(mitadPadre1,textoPadre1, "mitadPadre 1");
               // dibujar(mitadPadre2, textoPadre2, "mitadPadre 2");

                

                contador = 0;

                int compatibilidad = 0;
                int intentos = 0;
                

                while (compatibilidad == 0)
                {
                    if (esCompatible(mitadPadre1, mitadPadre2, "arriba"))
                    {
                        compatibilidad++;
                        elEngendroDelMal = unirSoluciones(mitadPadre1, mitadPadre2, "arriba");
                        if (evaluarCamino2D(elEngendroDelMal) <= evaluarCamino2D(elMejor))
                        {
                            elMejor = new List<int[]>();
                            elMejor.AddRange(elEngendroDelMal);
                        }
                    }

                    if (esCompatible(mitadPadre1, mitadPadre2, "abajo"))
                    {
                        compatibilidad++;
                        elEngendroDelMal = unirSoluciones(mitadPadre1, mitadPadre2, "abajo");
                        if (evaluarCamino2D(elEngendroDelMal) <= evaluarCamino2D(elMejor))
                        {
                            elMejor = new List<int[]>();
                            elMejor.AddRange(elEngendroDelMal);
                        }
                    }

                    if (esCompatible(mitadPadre1, mitadPadre2, "izquierda"))
                    {
                        compatibilidad++;
                        elEngendroDelMal = unirSoluciones(mitadPadre1, mitadPadre2, "izquierda");
                        if (evaluarCamino2D(elEngendroDelMal) <= evaluarCamino2D(elMejor))
                        {
                            elMejor = new List<int[]>();
                            elMejor.AddRange(elEngendroDelMal);
                        }
                    }

                    if (esCompatible(mitadPadre1, mitadPadre2, "derecha"))
                    {
                        compatibilidad++;
                        elEngendroDelMal = unirSoluciones(mitadPadre1, mitadPadre2, "derecha");
                        if (evaluarCamino2D(elEngendroDelMal) <= evaluarCamino2D(elMejor))
                        {
                            elMejor = new List<int[]>();
                            elMejor.AddRange(elEngendroDelMal);
                        }
                    }

                    if (compatibilidad == 0)
                    {
                        List<int[]> aux = girar90antihorario(mitadPadre2);

                        mitadPadre2 = new List<int[]>();
                        mitadPadre2.AddRange(aux);
                        intentos++;
                    }

                    if (intentos == 3)
                    {
                      //  intentos = 0;
                        List<int[]> aux = girarEspejoHorizontal(mitadPadre2);
                        mitadPadre2 = new List<int[]>();
                        mitadPadre2.AddRange(aux);
                    }
                    limite++;

                    if (limite == 100)
                    {
                        hayaMaldad = false;
                        limite = 0;
                        //Console.WriteLine("Hubo maldad");
                        break;
                        
                    }
                }
            }


           // dibujar(elMejor, this.texto, "El engendro del mal: " + this.evaluarCamino2D(elMejor)); 
            //Console.WriteLine(this.evaluarCamino2D(elMejor));

            return elMejor;
        }

        public void cruzamiento()
        {
            List<List<int[]>> p1 = new List<List<int[]>>();
            int participante1 = 0;
            int participante2 = 0;

            while (p1.Count < this.poblacion)
            {
                participante1 = generadorAleatorio.Next(this.poblacion);
                participante2 = generadorAleatorio.Next(this.poblacion);

                p1.Add(this.cruzar(pueblo[participante1], pueblo[participante2]));

            }//fin while

            pueblo = new List<List<int[]>>();
            pueblo.AddRange(p1);



        }

        public void seleccion()
        {

           List<List<int[]>> p1 = new List<List<int[]>>();
           int participante1 = 0;
           int participante2 = 0;

           while (p1.Count < this.poblacion)
           {
               participante1 = generadorAleatorio.Next(this.poblacion);
               participante2 = generadorAleatorio.Next(this.poblacion);

               if (evaluarCamino2D(pueblo[participante1]) < evaluarCamino2D(pueblo[participante2]))
               {
                   p1.Add(pueblo[participante1]);
               }
               else
               {
                   p1.Add(pueblo[participante2]);
               }
           }//fin while

           pueblo = new List<List<int[]>>();
           pueblo.AddRange(p1);


        }

        private List<int[]> unirSoluciones(List<int[]> padre1, List<int[]> padre2, string instruccion)
        {
            List<int[]> elNuevoSer = new List<int[]>();

            elNuevoSer.AddRange(padre1);

            int[] ultimaCoordenada = elNuevoSer[elNuevoSer.Count - 1];
            int[] coordenadaAnteriorPadre2 = padre2[0];

            // Console.WriteLine("Padre1: " + padre1.Count + ", Padre2: " + padre2.Count);


            if (instruccion == "arriba")
            {

                elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] + 1 });

            }
            else if (instruccion == "abajo")
            {
                elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] - 1 });

            }
            else if (instruccion == "derecha")
            {
                elNuevoSer.Add(new int[] { ultimaCoordenada[0] + 1, ultimaCoordenada[1] });

            }
            else
            {
                elNuevoSer.Add(new int[] { ultimaCoordenada[0] - 1, ultimaCoordenada[1] });

            }


            int contador = 0;
            foreach (int[] i in padre2)
            {
                if (contador++ == 0)
                    continue;

                coordenadaAnteriorPadre2 = padre2[contador - 2];
                ultimaCoordenada = elNuevoSer[elNuevoSer.Count - 1];


                //Console.WriteLine("Contador: " + contador);
                // Console.WriteLine("i = " + i[0] + "," +  i[1] + ", coordenadaAnteriorPadre2 = " + coordenadaAnteriorPadre2[0] + "," + coordenadaAnteriorPadre2[1]);
                if ((i[0] == coordenadaAnteriorPadre2[0] + 1) && (i[1] == coordenadaAnteriorPadre2[1]))
                {
                    //añadir nueva al elNuevoSer
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0] + 1, ultimaCoordenada[1] });
                    // Console.WriteLine("Agrego + X");
                }

                if ((i[0] == coordenadaAnteriorPadre2[0] - 1) && (i[1] == coordenadaAnteriorPadre2[1]))
                {
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0] - 1, ultimaCoordenada[1] });
                    // Console.WriteLine("Agrego -X");
                }

                if ((i[0] == coordenadaAnteriorPadre2[0]) && (i[1] == coordenadaAnteriorPadre2[1] + 1))
                {
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] + 1 });
                    // Console.WriteLine("Agrego +Y");
                }

                if ((i[0] == coordenadaAnteriorPadre2[0]) && (i[1] == coordenadaAnteriorPadre2[1] - 1))
                {
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] - 1 });
                    // Console.WriteLine("Agrego -Y");
                }
            }

            return elNuevoSer;
        }
        
        private List<int[]> girar90antihorario(List<int[]> camino)
        {
            int[] actualOriginal = new int[2];
            int[] siguienteOriginal = new int[2];
            int[] actualNueva = new int[2];
            int[] siguienteNueva = new int[2];
            int[] auxiliar = new int[2];
            List<int[]> caminoRotado = new List<int[]>();

            actualOriginal = camino[0]; //la primera
            caminoRotado.Insert(0, camino[0]);//añadiendo la primera tambien

            for (int i = 0; i < camino.Count - 1; i++)
            {
                actualOriginal = camino[i];
                siguienteOriginal = camino[i + 1];

                auxiliar = new int[] { actualOriginal[0], actualOriginal[1] + 1};

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta vertical para arriba

                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0] - 1, caminoRotado[i][1] });
                }

                auxiliar = new int[] { actualOriginal[0], actualOriginal[1] - 1 };

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta vertical para abajo
                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0] + 1, caminoRotado[i][1] });
                }

                auxiliar = new int[] { actualOriginal[0] + 1, actualOriginal[1]};

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta horizontal a la derecha -->
                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0], caminoRotado[i][1] + 1});
                }

                auxiliar = new int[] { actualOriginal[0] - 1, actualOriginal[1] };

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta horizontal a la izquierda <--
                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0], caminoRotado[i][1] - 1 });
                }

            }//fin for


                return caminoRotado;
        }

        private List<int[]> girarEspejoHorizontal(List<int[]> camino)
        {
            int[] actualOriginal = new int[2];
            int[] siguienteOriginal = new int[2];
            int[] actualNueva = new int[2];
            int[] siguienteNueva = new int[2];
            int[] auxiliar = new int[2];
            List<int[]> caminoRotado = new List<int[]>();

            actualOriginal = camino[0]; //la primera
            caminoRotado.Insert(0, camino[0]);//añadiendo la primera tambien

            for (int i = 0; i < camino.Count - 1; i++)
            {
                actualOriginal = camino[i];
                siguienteOriginal = camino[i + 1];

                auxiliar = new int[] { actualOriginal[0], actualOriginal[1] + 1 };

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta vertical para arriba

                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0], caminoRotado[i][1] + 1 });
                }

                auxiliar = new int[] { actualOriginal[0], actualOriginal[1] - 1 };

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta vertical para abajo
                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0], caminoRotado[i][1] - 1 });
                }

                auxiliar = new int[] { actualOriginal[0] + 1, actualOriginal[1] };

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta horizontal a la derecha -->
                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0] - 1, caminoRotado[i][1] });
                }

                auxiliar = new int[] { actualOriginal[0] - 1, actualOriginal[1] };

                if ((auxiliar[0] == siguienteOriginal[0]) && (auxiliar[1] == siguienteOriginal[1]))
                {
                    //Si esta horizontal a la izquierda <--
                    caminoRotado.Insert(i + 1, new int[] { caminoRotado[i][0] + 1, caminoRotado[i][1] });
                }

            }//fin for


            return caminoRotado;
        }

        private bool esCompatible(List<int[]> padre1, List<int[]> padre2, string instruccion)
        {
            bool bandera = true;


            List<int[]> elNuevoSer = new List<int[]>();

            elNuevoSer.AddRange(padre1);

            int[] ultimaCoordenada = elNuevoSer[elNuevoSer.Count - 1];
            int[] coordenadaAnteriorPadre2 = padre2[0];

           // Console.WriteLine("Padre1: " + padre1.Count + ", Padre2: " + padre2.Count);


            if (instruccion == "arriba")
            {

                elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] + 1 });
                
            }
            else if (instruccion == "abajo")
            {
                elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] - 1 });

            }
            else if (instruccion == "derecha")
            {
                elNuevoSer.Add(new int[] { ultimaCoordenada[0] + 1, ultimaCoordenada[1]  });

            }
            else
            {
                elNuevoSer.Add(new int[] { ultimaCoordenada[0] - 1, ultimaCoordenada[1]  });

            }


            int contador = 0;
            foreach (int[] i in padre2)
            {
                if (contador++ == 0)
                    continue;

                coordenadaAnteriorPadre2 = padre2[contador - 2];
                ultimaCoordenada = elNuevoSer[elNuevoSer.Count - 1];


                //Console.WriteLine("Contador: " + contador);
                // Console.WriteLine("i = " + i[0] + "," +  i[1] + ", coordenadaAnteriorPadre2 = " + coordenadaAnteriorPadre2[0] + "," + coordenadaAnteriorPadre2[1]);
                if ((i[0] == coordenadaAnteriorPadre2[0] + 1) && (i[1] == coordenadaAnteriorPadre2[1]))
                {
                    //añadir nueva al elNuevoSer
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0] + 1, ultimaCoordenada[1] });
                    // Console.WriteLine("Agrego + X");
                }

                if ((i[0] == coordenadaAnteriorPadre2[0] - 1) && (i[1] == coordenadaAnteriorPadre2[1]))
                {
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0] - 1, ultimaCoordenada[1] });
                    // Console.WriteLine("Agrego -X");
                }

                if ((i[0] == coordenadaAnteriorPadre2[0]) && (i[1] == coordenadaAnteriorPadre2[1] + 1))
                {
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] + 1 });
                    // Console.WriteLine("Agrego +Y");
                }

                if ((i[0] == coordenadaAnteriorPadre2[0]) && (i[1] == coordenadaAnteriorPadre2[1] - 1))
                {
                    elNuevoSer.Add(new int[] { ultimaCoordenada[0], ultimaCoordenada[1] - 1 });
                    // Console.WriteLine("Agrego -Y");
                }
            }



          //  dibujar(elNuevoSer, this.texto, "El nuevo ser");

            for (int x = 0; x < elNuevoSer.Count - 1; x++ )
            {
                for (int y = 1; y <= elNuevoSer.Count - 1; y++)
                {

                    if ((elNuevoSer[x][0] == elNuevoSer[y][0]) && (elNuevoSer[x][1] == elNuevoSer[y][1]))
                    {
                        //Console.WriteLine(x + " = " + y);
                        if(x != y)
                            bandera = false;
                    }

                }

                

            }//fin for

            //dibujar(elNuevoSer, this.texto, "El nuevo ser: " + bandera); 


            return bandera;
        }
        public void pruebas()
        {


            

            //MessageBox.Show("Generados");
        }

        public void dibujar(List<int[]> camino,string entrada,  string titulo)
        {

            forma1 forma = new forma1(camino, entrada, titulo, new ArrayList());
            forma.ShowDialog();

        }

        public List<int[]> mejorSolucion()
        {

            List<int[]> elMachin = new List<int[]>();
            elMachin.AddRange(pueblo[0]);
            foreach (List<int[]> i in pueblo)
            {
                if (evaluarCamino2D(i) < evaluarCamino2D(elMachin))
                {
                    elMachin = new List<int[]>();
                    elMachin.AddRange(i);
                }
            }


            return elMachin;
        }
    }
}
